package weekthree;

import java.util.ArrayList;
import java.util.List;

public class LetterCombinationsOfPhoneNumber_17 {
    List<String> ans;
    List<char[]> edges;
    List<Character> str;

    public List<String> letterCombinations(String digits) {
        ans = new ArrayList<>();
        if (digits.length() == 0) return ans;
        char[] phone = digits.toCharArray();
        str = new ArrayList<>();
        edges = new ArrayList<>();
        edges.add(new char[]{'a', 'b', 'c'});
        edges.add(new char[]{'d', 'e', 'f'});
        edges.add(new char[]{'g', 'h', 'i'});
        edges.add(new char[]{'j', 'k', 'l'});
        edges.add(new char[]{'m', 'n', 'o'});
        edges.add(new char[]{'p', 'q', 'r', 's'});
        edges.add(new char[]{'t', 'u', 'v'});
        edges.add(new char[]{'w', 'x', 'y', 'z'});

        dfs(phone, 0);
        return ans;
    }

    private void dfs(char[] phone, int index) {
        if (index == phone.length) {
            StringBuilder sb = new StringBuilder();
            for (char c : str) {
                sb.append(c);
            }
            ans.add(sb.toString());
            return;
        }

        int num = phone[index] - '0';
        for (char ch : edges.get(num - 2)) {
            //str 加上字符ch
            str.add(ch);
            dfs(phone, index + 1);
            //恢复list
            str.remove(str.size() - 1);
        }
    }
}

